//
// Created by francklinson on 2021/5/24.
//
#include <vector>
#include <string>
#include <iostream>

using namespace std;

class Solution {
public:
    vector<int> minOperations(string boxes) {
        int n = (int) boxes.size();
        vector<int> ans(boxes.size(), 0);
        for (int i = 0; i < n; ++i) {
            int temp = 0;
            for (int j = 0; j < n; ++j) {
                if (j == i) continue;
                if (boxes[j] == '1') {
                    temp += abs(j - i);
                }
            }
            ans[i] = temp;
        }
        return ans;
    }

    vector<int> minOperations2(string boxes) {
        int n = (int) boxes.size();
        vector<int> ans(boxes.size(), 0);
        for (int i = 0; i < n; ++i) {
            if (boxes[i] == '1') {
                for (int j = 0; j < n; ++j) {
                    if (j != i) {
                        ans[j] += abs(i - j);
                    }
                }
            }
        }
        return ans;
    }

    vector<int> minOperations3(string boxes) {
        vector<int> answer(boxes.size());
        int left = 0, right = 0, total = 0;//左边盒子的个数，右边盒子的个数，操作数
        //计算第一个盒子的操作数
        if (boxes[0] == '1') left++;
        for (int i = 1; i < boxes.length(); i++) {
            if (boxes[i] == '1') {
                right++;
                total += i;
            }
        }
        answer[0] = total;
        //根据前一个盒子的操作数，计算下一个盒子的操作数
        for (int i = 1; i < boxes.length(); i++) {
            total = total + left - right;
            if (boxes[i] == '1') {
                left++;
                right--;
            }
            answer[i] = total;
        }
        return answer;
    }
};

int main() {
    Solution sol;
    auto ans = sol.minOperations3("110");
    for (auto &x:ans) cout << x << endl;
    return 0;
}
